﻿// 212. 计数交换.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://www.acwing.com/problem/content/214/

给定一个 1∼n的排列 p1,p2,…,pn
，可进行若干次操作，每次选择两个整数 x,y，交换 px,py。

设把 p1,p2,…,pn变成单调递增的排列 1,2,…,n至少需要 m次交换。

求有多少种操作方法可以只用 m次交换达到上述目标。

因为结果可能很大，你只需要输出结果对 109+9取模之后的值。

例如排列 2,3,1 至少需要 2 次交换才能变为 1,2,3。

操作方法共有 3 种，分别是：

方法一：先交换数字 2,3，变成 3,2,1，再交换数字 3,1，变成 1,2,3。
方法二：先交换数字 2,1，变成 1,3,2，再交换数字 3,2，变成 1,2,3。
方法三：先交换数字 3,1，变成 2,1,3，再交换数字 2,1，变成 1,2,3。

输入格式
第一行包含整数 T，表示一共有 T组测试用例。
每个测试用例前都会有一个空行。
每个测试用例包含两行，第一行包含整数 n。

第二行包含 n个整数，表示序列 p1,p2,…,pn。

输出格式
每个测试用例输出一个结果，每个结果占一行。

数据范围
1≤n≤105
输入样例：
3

3
2 3 1

4
2 1 4 3

2
1 2
输出样例：
3
2
1
*/



int main()
{
    std::cout << "Hello World!\n";
}
 